The aim of the invention is to support automatic modeling, analysis (verification) and real-time simulation of large-scale configuration problems on a standard computer (e.g. a personal computer). Mathematically speaking, such problems on finite domains or intervals can be expressed in terms of truth tables with MN combinations, each of which can assume either of the truth-values true or false (legal or non-legal). Here we are assuming N variables, each with M elements. Thus, binary variables are to be considered as a special case with M=2.
Obviously, MN combinations will cause xe2x80x9ccombinational explosionxe2x80x9d and it is therefore not a trivial task to solve large configuration problems with a multitude of variables. Nevertheless, the present invention makes it possible to unify the seemingly contradictory requirements for completeness (all combinations must be accessible to ensure logical consistency) with compactness of representation and speed of simulation.
For example, interlocking systems for railway operation are controlled by several thousands variables representing signal values or switch positions. To illustrate, even a small interlocking system with 2000 binary variables will be characterized by the huge number of 22000 states or combinations. Some combinations are legal (allowed), while other combinations are clearly illegal because they would cause disasters. To handle these systems with conventional technology, it has been necessary to break down the system into subsystems of sufficiently small size to allow their validation, whereby not only illegal, but also a large number of legal combinations may be excluded, resulting in a less efficient utilization of the system. In general, the system variables will not be limited to binary values but will also include different data types on finite domains (e.g. multi-valued logic, integers, or finite sets of intervals). It is highly desirable to be able to handle configuration problems in systems of that size by means of computerized tools which could provide complete and correct responses almost instantaneously.
Another example is configuration of products or services (e.g. cars, computers or travels) on the Internet. Many products are available in a multitude of variants, which must be selected by the customer from a number of mutually dependent options. Thus, only some combinations of these options are possible or legal, while other combinations are illegal due to some technical or commercial constraints. It is therefore desirable to design e-commerce tools to enable the user to select interactively only the legal combinations, even from very complex product models.
While a number of computerized configuration tools have become available, e.g. the systems disclosed in WO 90/09001 and U.S. Pat. No. 5,515,524 there is still a demand for systems which fulfil the requirements for completeness and compactness and speed of response. In this context, the term xe2x80x9ccompletenessxe2x80x9d indicates the mathematical requirement that all combinations have been verified to ensure logical consistency.
The present invention provides an elegant solution to this problem without the problem of xe2x80x9ccombinational explosionxe2x80x9d. As it will be understood from the following description, the crux of the invention is the establishment of a novel type of database, in the following termed an xe2x80x9carray databasexe2x80x9d. While the database is an optimal tool for the complex configuration problems indicated above and described in greater in the following, it will be understood that due to its unique inherent advantages, it is also useful for a wide range of applications for which conventional database systems, typically relational databases, are used at present.
A scientific/mathematical discussion of principles relevant to the invention is given in Moller, Gert L.: On the Technology of Array-based Logic. Ph.D. thesis, Electric Power Engineering Department, Technical University of Denmark, January 1995.
In one aspect, the invention relates to a method for generating a database useful for configuring and/or optimizing a system spanned by variables on finite domains and/or intervals, said method comprising generating and storing, in a memory or storage medium of a computer, an addressable configuration space of the entire system in terms of all legal Cartesian subspaces of states or combinations satisfying the conjunction of substantially all system constraints on all variables, with all interconnected legal Cartesian subspaces being addressable as legal combinations of indices of link variables, so as to establish a database in which substantially all legal solutions in the system are stored as nested arrays.
In the following, the database generated according to the invention will be termed an xe2x80x9carray databasexe2x80x9d, this term reflecting the fact that all legal solutions are stored in the database as one or more nested arrays.
Definitions and explanations relevant to some of the terms used in the present specification and claims are as follows:
xe2x80x9cConfiguringxe2x80x9d means establishing substantially all legal combinations of the variables satisfying substantially all the constraints on the system. Preferably, all legal combinations of the variables satisfying all the constraints on the system are established, in which preferred case the legal Cartesian subspaces of states or combinations will satisfy the conjunction of all system constraints on all interconnected variables.
xe2x80x9cOptimizingxe2x80x9d means applying a heuristic selection of combinations within a set of legal combinations.
The term xe2x80x9ca system spanned by variables on finite domains and/or intervalsxe2x80x9d indicates that each variable of the system consists of a finite set of elements or state values (e.g., logical truth values) or a finite set of intervals.
The term xe2x80x9cAn addressable configuration spacexe2x80x9d indicates that substantially all legal combinations are explicitly represented; in the preferred case, all legal combinations are explicitly represented.
xe2x80x9cA Cartesian subspacexe2x80x9d is a compact representation of one or more legal combinations, all combinations being derivable/calculated/ as the Cartesian product of the elements or state values for each variable.
xe2x80x9cSystem constraintsxe2x80x9d are the relations (propositional functions) on variables defined for the system.
xe2x80x9cInterconnecting variablesxe2x80x9d indicates variables present in at least two relations.
xe2x80x9cA link variablexe2x80x9d means a variable generated by the method according to the invention and added to a given relation with a unique index which identifies one Cartesian subspace.
xe2x80x9cInterconnected legal Cartesian subspacesxe2x80x9d means legal Cartesian subspaces with at least one common variable.
It is a crucial feature of the invention that all illegal states or combinations violating the system constraints are excluded from the relations. Such exclusion of illegal states or combinations can preferably be performed while the database is generated by the method according to the invention, the illegal states or combinations being excluded whenever identified. A state of contradiction or inconsistency is present in a system if just one relation of the system has no legal combination or state. On the other hand, a system is said to be consistent if at least one state or combination is legal, i.e. satisfying all system constraints. If, in the generation of the database, just one relation of a system is found to have no legal combination or state, then that whole system is in a state of contradiction or inconsistency and must be excluded.
In the following, the process of colligating relations (that is, combining relations to arrive at a more complex subsystem or system) is discussed in greater detail. It will be understood that on each level of the colligation process, inconsistencies or contradictions will be identified and will, thus, result in exclusion of the colligated subsystem or system. Thus, when the generating process has been completed, the system will be consistent, as manifested by all relations having at least one legal Cartesian subspace.
In the present specification and claims, the term xe2x80x9csystemxe2x80x9d is used about an entire system of variables or, alternatively, about a part of an entire system of variables. In all cases relevant to the present invention, the system, understood in this manner, is completely defined in that every combination under the system is either legal or illegal with respect to all system constraints relevant to the use of the database and preferably with respect to absolutely all system constraints. Thus, the term system, used about an entire system of variables, indicates, in the context of the claims and the specification, that the entire system is completely defined with respect to all system constraints relevant to the use of the database, and preferably with respect to absolutely all system constraints. When a system of variables is not completely defined in the above sense of this term, then only that part of the system which is in fact completely defined is covered by the tern xe2x80x9csystemxe2x80x9d as used in the claims. The term xe2x80x9csubstantiallyxe2x80x9d, as used in claim 1, indicates that it is possible to have a system which is not defined with respect to system constraints that are not relevant to the use of the database. The them xe2x80x9csubstantiallyxe2x80x9d can also indicate a system in which the process of colligation has not been completed, and where the runtime environment must be adapted to perform certain tests for consistency. While the latter variant is not considered ideal, it may nevertheless apply for certain applications of the invention where the realtime capability of the runtime environment is not a requirement.
As indicated above, the system constraints may be determined by conjugating one or more relations, each relation representing the legal Cartesian subspaces of states or combinations on a given subset of variables. The conjugation of the one or more relations comprises calculating the Cartesian subspaces satisfying the combined constraints of the one or more relations. If no relations have common variables, no further action is required to conjugate the relations.
According to an important preferred feature of the invention, all relations with at least one common variable are colligated. The colligation comprises conjugating the constraints of two or more relations being connected by having common variables to establish the Cartesian subspace(s) satisfying the combined constraints of the two or more relations.
The colligation of the two or more relations will normally be performed by joining the two or more relations up to a predetermined limit. Joining comprises the operation of replacing a set of relations with a single relation satisfying the combined constraints of the set.
The set of relations is not limited to two relations but can in general be any finite number of relations. In a preferred embodiment of the invention the case where three or more relations are joined is typically decomposed into a number of pairwise joins. This pairwise joining can comprise a predetermined strategy or the joining can be in a random order.
The joining process will typically reduce the number of relations, and the resulting number of relations are then colligated by linking them and grouping them into one or more cluster(s) of relation(s).
A cluster can comprise one relation or a set of interconnected relations. These clusters will be described in greater detail in the following.
The linking of the relations consists of adding link variables and adding one or more calculated relation(s) representing the constraints on the link variables.
The linking of relations can be within a cluster or between clusters. The linking between two clusters may be performed by establishing a link relation comprising two link variables, while for a linking within a cluster the link relation(s) comprises all link variables on the relations in the cluster.
If three or more relations interconnected with common variables are generating cycles or closed paths, then they are grouped into a single cluster comprising the three or more relations. As a consequence the resulting cluster(s) are interconnected without cycles, i.e. in a tree structure.
The tree structure makes it possible to ensure completeness of deduction in the run time environment by state propagation, for example when a configuration or optimization is performed.
The term xe2x80x9ccompleteness of deductionxe2x80x9d indicates that all logical consequences must be deduced on one or more variables. In important embodiments of the invention, the completeness of deduction relates to all logical consequences on all variables, but as indicated above, the invention is not limited to that.
When the array database is to be used for optimization, one or more object functions are incorporated. An object function of a given subset of variables, the object function deriving characteristics of the given subset of variables, is linked to the complete configuration space by deducing the constraints imposed by the object function on each link variable connected to the given subset of variables.
After the array database has been generated by the method according to the invention, object functions can provide information between a set of variables and a set of object function values, e.g., price, weight, color.
If a set of object function values does not have a xe2x80x9cnaturalxe2x80x9d order, e.g. as numbers, an arbitrary order can be assigned to the set of object function values.
The characteristics of the object function may be determined and the constraints on the link variables deduced on each combination of the given variables, the result being represented as a relation on the object function, the given variables, and the link variables.
These characteristics can be the values of the object function given by functional mapping of a set of independent variables or a set of constrained variables. The mapping can also be a general relation yielding one or more object function values for each combination of the variables.
In another aspect, the invention relates to a method for configuring and/or optimizing a system spanned by variables on finite domains, said method comprising
providing a database in which substantially all legal solutions in the system are stored as nested arrays and
deducing any subspace, corresponding to an input statement and/or inquiry, of states or combinations spanned by one or more variables of the system represented by the nested arrays by deriving the consequences of a statement and/or an inquiry by applying the constraints defined by the statement and/or inquiry to the database.
xe2x80x9cDeducingxe2x80x9d means deriving or determining all logical inferences or conclusions from a given set of premises, i.e. all the system constraints.
xe2x80x9cInquiryxe2x80x9d means a question for which the array database can provide all answers.
A question could be about the legal combination(s) of a given set of variables satisfying the system constraints and possibly also satisfying an external statement.
An external statement can be a number of asserted and/or measured states and/or constraints from the environment.
Thus, a deduction of any subspace of states or combinations is performed on a given subset of variable(s) either without or colligated with asserted and/or measured states and/or constraints from the environment.
The interaction between the system represented by the array database and the environment is suitably performed by means of a state vector (SV) representing all legal states or values of each variable.
Thus, an input state vector (SV1) may represent the asserted and/or measured states from the environment, while an output state vector (SV2) may represents deduced consequence(s) on each variable of the entire system when the constraints of SV1 are colligated with all system constraints in the array database.
The deduction can be performed by consulting one or more relation(s) and/or one or more object function(s) at a time by colligating the given subset of variables in the relation with the given subsets of states in the state vector and then deducing the possible states of each variable.
The consultation of a relation can be performed by colligating, e.g. joining, the relation and the states of the variables present in the relation. The result of the consultation can be the projection (union of all elements) on each variable of the colligated relation, or the result can be the colligated relation. The colligation can of course be a joining, but it should be evident from the discussion given herein that the consultation of each relation is not limited thereto.
In a preferred embodiment of the invention two or more variables are colligated in parallel; the projection on two or more variables can similarly be performed in parallel. The invention is not limited to such parallel implementation, and the invention can just as well be implemented sequentially.
In one embodiment of the invention completeness of deduction is obtained by consulting connected relations, until no further consequences can be deduced on any link variable. This operation is termed xe2x80x9cstate propagationxe2x80x9d. Such state propagation comprises consulting two or more relations in parallel. The invention is of course not limited to such parallel implementation, and, due to the cluster structure, the invention can just as well be implemented sequentially.
An important feature of the configuration and/or optimization according to the invention is that the state of contradiction can be identified, when no legal states or values are deduced when consulting at least one relation.